# 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
#
#  示例 1：
# 输入：head = [1,2,3,4,5], k = 2
# 输出：[4,5,1,2,3]
#
#  示例 2：
# 输入：head = [0,1,2], k = 4
# 输出：[2,0,1]
#
#  示例 3：
# 输入：head = [1,2], k = 1
# 输出：[2, 1]
from typing import Optional

from com.example.linked.common import *


class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next or k == 0:
            return head
        cur, lens = head, 1
        while cur and cur.next:  # 计算长度
            lens += 1
            cur = cur.next
        tail = cur  # 记录尾部指针(方便形成环)
        rotateCount = lens - k % lens

        if rotateCount == lens:  # 旋转次数是链表长度的整倍数，即不需要旋转，直接返回即可
            return head
        # 否则，先将链表形成环，然后在适当的地方(结果头节点)将环断开，返回即可
        tail.next = head
        while rotateCount > 0:
            cur = cur.next
            rotateCount -= 1
        resHead = cur.next
        cur.next = None
        return resHead


if __name__ == '__main__':
    head, k = getListNode(1, 2, 3, 4, 5), 2
    res = Solution().rotateRight(head, k)
    vistListNode(res)
    print()

    # head = [0,1,2], k = 4
    head, k = getListNode(0, 1, 2), 4
    res = Solution().rotateRight(head, k)
    vistListNode(res)
    print()

    head, k = getListNode(1, 2), 1
    res = Solution().rotateRight(head, k)
    vistListNode(res)
